#!/usr/bin/python
# Filename: digit_maze.py

# a problem from C Examples 100, the 100th problem
# there is a maze of 3*3 blanks, and digit 1~8 is random filled in outer 8 blanks
# each pair of physical near blanks are connected
# a digit can move between connected blanks if the target one is empty

# the solution is much like insert sort
# the solution won't move number 1
# if number 1 can be moved, we can first find a most-longest-in-order sub-sequence, then move the others

maze = [2, 3, 1, 6, 0, 4, 8, 7, 5]

def print_maze(maze):
    for i in range(3):
        print maze[i*3:i*3+3]
    print "----------"

print_maze(maze)

l = [0, 1, 2, 5, 8, 7, 6, 3]
# find 1
pos1 = maze.index(1)
# l shows the right position when finish, from 1 to 8, l[i-1] is the right position of number i
l = l[pos1:] + l[:pos1]

for i in range(2, 9):
    # insert i to the right position (maze[l[i-1]])
    # pos and tar are sequence numbers, l[pos] and l[tar] are the real positions in maze
    pos = l.index(maze.index(i))
    tar = i-1
    if pos == tar: continue # already in right position
    # maze[4], the center of maze, is used as temp storage
    maze[4], maze[l[pos]] = maze[l[pos]], maze[4]
    print_maze(maze)
    # switch as insert sort
    for j in range(pos, tar, -1):
        maze[l[j-1]], maze[l[j]] = maze[l[j]], maze[l[j-1]]
        print_maze(maze)
    maze[4], maze[l[tar]] = maze[l[tar]], maze[4]
    print_maze(maze)
